
local function _concat(arr1, arr2)
    for _, v in ipairs(arr2) do
        arr1[#arr1+1] = v
    end
    return arr1
end

-- the return array is in a ascending order
local function _quicksort(array)
    if #array < 2 then
        return array
    end

    local pivot = array[1]
    local less, greater = {}, {}
    for i=2, #array do
        if array[i] <= pivot then
            less[#less+1] = array[i]
        else
            greater[#greater+1] = array[i]
        end
    end

    return _concat(_quicksort(less), _concat({pivot}, _quicksort(greater)))
end

local function test()
    local tb = {1000, -100, 1, 10, 5}
    local ret = _quicksort(tb)
    local n = #ret
    local i = 1
    while i < n do
        if ret[i] > ret[i+1] then
            break
        end
        i = i + 1
    end
    assert(i == n)
end

test()

